import java.io.IOException;
import java.io.UnsupportedEncodingException;
import java.math.BigDecimal;
import java.security.Signature;
import java.util.Arrays;
import java.util.Random;

/**
 * @author LKQ
 * @date 2022/4/13 14:24
 * @description 记录一些常用的方法
 * 乘法取模具有分配律：(a*b) mod m = [(a mod m) * (b mod m)] mod m
 */
public class MyMath {

    /**
     * 判断一个数是否为奇数。注意不能使用 i % 2 == 1这个表达式，因为当i为负奇数的时候，i % 2 = -1.
     * 当取余操作返回一个非零的结果时，它与左操作符具有相同的正负符号。
     *
     * @param i int i
     * @return true or false
     */
    public static boolean isOdd(int i) {
        return (i & 1) != 0;
    }

    /**
     * 求两个数之间的最大公约数 gcd (greatest common divisor)
     * 若 gcd(i, j) == 1，那么i, j构成最简分数
     *
     * @param a a
     * @param b b
     * @return 最大公约数
     */
    public long gcd(long a, long b) {
        return b != 0 ? gcd(b, a % b) : a;
    }


    /**
     * 求两个数之间的最小公倍数 lcm (least common multiple)
     *
     * @param a a
     * @param b b
     * @return 最小公倍数
     */
    public long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    /**
     * 判断一个整数是否是2的幂
     *
     * @param n n
     * @return true or false
     */
    public boolean isPowOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }

    /**
     * 统计 0 ~ X之间的奇数个数
     *
     * @param x 大于0的数
     * @return odd个数
     */
    public int oddCount(int x) {
        return (x + 1) / 2;
    }

    /**
     * 从n个数中取出2个，有多少种组合
     *
     * @param n n
     * @return 组合数
     */
    public int C2(int n) {
        return (n * (n - 1)) / 2;
    }

    /**
     * 返回 最低位1代表的整数, 如 1100 的补码 为 0011 + 1 = 0100， 1100 & 0100 = 0100 保留最地位整数
     *
     * @param x x
     * @return 最低位 1 代表的整数
     */
    public int lowBit(int x) {
        return x & -x;
    }

    /**
     * 二分查找模板，蓝红区间二分法，可以很好的处理类似问题
     * 1.查找第一个 >= k的 元素
     * 2.查找最后一个 < k 的 元素
     * 3.查找第一个 >k 的 元素
     * 4.查找最后一个 <= k的 元素
     * 时间复杂度 O(nlogn)
     *
     * @param nums 已经排好序的 nums数组
     * @param k    待查找元算
     * @return l 或 r
     */
    public int binarySearch(int[] nums, int k) {
        // 细节1， 为了处理全是蓝色区间或全是红色区间，l, r取值为 -1，n，l标记蓝色区间，r标记红色区间
        int l = -1, r = nums.length;
        // 细节2. l + 1 != r保证 l r最后相邻，而不会相等
        while (l + 1 != r) {
            // mid 最小值，l = -1, r = 1, mid为0， mid最大值，r = n, l = n-2, mid = n-1, 一直在区间内
            int mid = (l + r) / 2;
            // 判断条件为蓝色区间，如第一个问题，那么条件 < k, 返回 r, 如第二个问题，那么条件就是 < k, 但是返回值为 l
            if (nums[mid] < k) {
                l = mid;
            } else {
                r = mid;
            }
        }
        // 返回 l 或者 r，这个需要确定好
        return l;
    }

    /**
     * 求 a^n次方，快速幂解决方法。时间复杂度为 O(logN)
     *
     * @param a a
     * @param n n
     * @return n 个 a 相乘
     */
    public long binExp(int a, int n) {
        long r = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                r = r * a;
            }
            a = a * a;
            n >>= 1;
        }
        return r;
    }

    /**
     * 计算两点之间的曼哈顿距离
     *
     * @param point1 p1
     * @param point2 p2
     * @return dis(A, B) = |xa - xb| + |ya - yb|
     */
    public int manhattanDistance(int[] point1, int[] point2) {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    }


    /**
     * 判断一个数是否为完全平方数
     *
     * @param x x
     * @return a * a == x
     */
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);
        return y * y == x;
    }

    /**
     * 判断一个整数是否是回文数
     *
     * @param x x
     * @return boolean
     */
    public boolean isPalindrome(int x) {
        // 特殊情况：如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0  只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        // 反转一半数字，
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }

    /**
     * 埃氏筛法：判断小于n的所有正整数中，质数的个数，时间复杂度为O(Nlog(logN))
     *
     * @param n n
     * @return sum(primes < n), primes为质数，如2，3，5，7
     */
    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        // 1代表是质数
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                if ((long) i * i < n) {
                    // 2的所有倍数，3的倍数
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }

    /**
     * 矩阵乘法 只有在第一个矩阵的列数和第二个矩阵的行数相等时才有意义
     *
     * @param matA (m, k)
     * @param matB (k, n)
     * @return res (m, n)
     */
    public int[][] matMultiply(int[][] matA, int[][] matB) {
        int m = matA.length, n = matB[0].length;
        int[][] res = new int[m][n];
        int r = 0;
        for (int i = 0; i < matA.length; i++) {
            for (int k = 0; k < matA[0].length; k++) {
                r = matA[i][k];
                for (int j = 0; j < matB[0].length; j++) {
                    res[i][j] += r * matB[k][j];
                }
            }
        }
        return res;
    }

    /**
     * 牛顿迭代法求一个数的正平方根, 同立方根
     *
     * @param n n
     * @return x^2 = n;
     */
    public static double mySqrt(double n) {
        if (n == 0) {
            return 0;
        }
        double C = n, x0 = n;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (Math.abs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return x0;
    }

    /**
     * 获取一个数的立方根, 利用泰勒公式展开，f(x) = f(xo) + f`(xo) ( x - xo) = 0, 其中 f(x) = x^3 - C = 0
     *
     * @param n n
     * @return x^3 = n
     */
    public static double getCubeRoot(double n) {
        if (n == 0) {
            return 0;
        }
        boolean isNegative = n < 0;
        if (n < 0) {
            n = -n;
        }
        double C = n, x0 = n;
        while (true) {
            double xi = x0 * 2 / 3 + C / (3 * x0 * x0);
            if (Math.abs(x0 - xi) < 1e-9) {
                break;
            }
            x0 = xi;
        }
        return isNegative ? -x0 : x0;
    }

    public static void main(String[] args) {
        try {
            System.out.println("1");
        }catch (Exception e) {
            System.out.println(2);
        }
    }

}
